class Solution
{
public:
    int nthMagicalNumber(int n, int a, int b)
    {
        long long abLcm = lcm(static_cast<long long>(a), static_cast<long long>(b));
        auto magicCount = [=](long long x) -> long long
        {
            return x / a + x / b - x / abLcm;
        };
        long long lower = 1;
        long long upper = static_cast<long long>(n) * max(a, b);
        while (lower < upper)
        {
            long long mid = (lower + upper) / 2;
            long long maigcID = magicCount(mid);
            if (maigcID >= n)
            {
                upper = mid;
            }
            else
            {
                lower = mid + 1;
            }
        }

        return lower % 1000000007;
    }
};